package games.eightPuzzle;

import games.eightPuzzle.heuristics.AStarMD;
import games.eightPuzzle.heuristics.DummyHeuristic;
import games.eightPuzzle.heuristics.Heuristic;
import games.eightPuzzle.heuristics.ImprovedMDHuristic;

import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.Random;

import commonDataStructures.BinaryHeap;
import commonDataStructures.PQueue;
import commonDataStructures.PSingleCollection;
import commonDataStructures.PStack;
import commonDataStructures.PrimitiveCollection;
import commonDataStructures.PrimitiveQueue;

import games.eightPuzzle.states.SlidingPuzzleState;

public class SlidingPuzzle implements Runnable{

	private static final int MINIMIZE_FACTOR = 2;

	private static int processes = 0;
	private static int terminatedProcesses = 0;

	private SlidingPuzzleState _startState = null;
	private SlidingPuzzleState _finalState = null;
	private PrimitiveCollection<SlidingPuzzleState> _bank;

	private boolean _reversed = false;


	/**
	 * ctor
	 * @param bank
	 * @param sState
	 * @param fState
	 */
	public SlidingPuzzle(PrimitiveCollection<SlidingPuzzleState> bank, SlidingPuzzleState sState, SlidingPuzzleState fState){
		_bank = bank;
		_startState = sState;
		_finalState = fState;
	}


	/**
	 * set if the problem is reversed or strightforwards
	 * @param reversed
	 */
	public void setReversed(boolean reversed){
		_reversed = reversed;
	}

	private SlidingPuzzleState getNextState(){
		ArrayList<SlidingPuzzleState> tbank = new ArrayList<SlidingPuzzleState>();
		tbank.add(_bank.remove());
		while (!_bank.isEmpty()){
			SlidingPuzzleState s = _bank.remove();
			if (s.compareTo(tbank.get(0))!=0){
				_bank.insert(s);
				break;
			}else{
				tbank.add(s);
			}
		}
		Random rnd = new Random();
		SlidingPuzzleState ret = tbank.remove(rnd.nextInt(tbank.size()));
		for(SlidingPuzzleState s:tbank){
			if (rnd.nextInt(2)==0)_bank.insert(s);
		}
		return ret;
	}
	/**
	 * find a solution to a given problem
	 * @param hasLimit if there is a limit on the algorithem
	 * @param maxExpantion what is the limit of nodes expandtion
	 * @return
	 */
	private SolutionInfo findSolution(boolean hasLimit,long maxExpantion){
		//		collection to the states we have encountered already
		//to avoid multiply states
		HashMap<String, String> encounteredStates = new HashMap<String, String>();

		long moves = 0;

		//add the first state to the states list and to the encounteredStates list
		_bank.insert(_startState);
		encounteredStates.put(_startState.getHash(),null);

		//checks the capacity of the heap and set the memory 
		//limit to 0.1% of the heap
		double memLimit = Runtime.getRuntime().freeMemory()*0.001;

		boolean found = false;
		SlidingPuzzleState state=null;

		long startingTime = new Date().getTime();

		while(!_bank.isEmpty() && !(hasLimit && maxExpantion < moves)){

			//check of heap overflow, if free memory is under the
			//memory limit, throw the less intresting states to avoid
			//heap overflow
			if (Runtime.getRuntime().freeMemory()< memLimit){
				encounteredStates.clear();
				int newSize = _bank.size()/MINIMIZE_FACTOR;
				PrimitiveCollection<SlidingPuzzleState> n = null;
				if (_bank instanceof BinaryHeap){
					n = new BinaryHeap<SlidingPuzzleState>();
					for(int i=0;i<newSize;i++){
						SlidingPuzzleState s = _bank.remove();
						n.insert(s);
						encounteredStates.put(s.getHash(), null);
					}
					_bank = n;
				}else{
					PrimitiveQueue<SlidingPuzzleState> tmpQ = new PrimitiveQueue<SlidingPuzzleState>();
					for(int i = 0;i<newSize;i++){
						SlidingPuzzleState s = _bank.remove();
						tmpQ.insert(s);
						encounteredStates.put(s.getHash(),null);
					}
					_bank = tmpQ;
				}

				//if reducing the states bank is not helping, return
				//no solution has been found
				if (Runtime.getRuntime().freeMemory()< memLimit){
					return new SolutionInfo(null,moves,Integer.MAX_VALUE,_reversed);
				}
			}

			
			state = getNextState();//_bank.remove();
			System.out.println(state.toString());
			//state = _bank.remove();
			//System.out.println(state.toString());
			++moves;
			SolutionBank.ctr++;
			//checks if we reached the goal state
			if (state.equals(_finalState)){
				found = true;
				break;
			}

			//get the next possible moves from the current state
			ArrayList<SlidingPuzzleState> nextMoves = state.getPossibleNextMoves();
			if(_bank instanceof PSingleCollection){
				_bank.init();
			}
			//add only the "new to us" states 
			for(SlidingPuzzleState nState : nextMoves){
				if (!encounteredStates.containsKey(nState.getHash())){
					_bank.insert(nState);
					encounteredStates.put(nState.getHash(), null);
					SolutionBank.ctr++;
				}
			}
		}

		if (!found){
			return new SolutionInfo(null,moves,Integer.MAX_VALUE,_reversed);
		}

		return new SolutionInfo(state.getTrace(),moves,new Date().getTime()-startingTime,_reversed);
	}

	/**
	 * find solution (no limits on the algorithem)
	 * @return
	 */
	public SolutionInfo findSolution(){
		return findSolution(false,0);
	}

	/**
	 * find solution with a limit of max nodes expandtion
	 * @param expandtionLimit
	 * @return
	 */
	public SolutionInfo findSolution(long expandtionLimit){
		return findSolution(true, expandtionLimit);
	}


	/**
	 * terminate the process
	 * @param sol
	 */
	private void terminate(SolutionInfo sol){
		terminatedProcesses++;
		//process didnt find solution, but other procuess are running
		if (!sol.hasSolution()&&terminatedProcesses<processes){
			return;
		}

		//if a solution has been found add it
		if (sol.hasSolution()){
			SolutionBank.addSolution(sol);
		}

		//checks if there are other processes that running
		//if such processes exist, wait a period of time that
		//equals to the preiod who took to the current process
		//to find the solution and then, print the best solution
		//and exit.
		if (terminatedProcesses<processes){
			try{
				Thread.currentThread().wait(sol.getTime());
			}catch(Exception e){}
		}
		SolutionBank.loadFinalSolution();
		SolutionBank.printSolution();
	}

	/* (non-Javadoc)
	 * @see java.lang.Runnable#run()
	 */
	public void run() {
		processes++;
		terminate(findSolution());
	}

	public SolutionInfo runTest(int branchingFactor)
	{
		Heuristic totalFunction = new AStarMD();
		Heuristic h = new ImprovedMDHuristic(_finalState,branchingFactor);
		_startState.setHeuristics(h, totalFunction);
		_finalState.setHeuristics(h, totalFunction);
		
		return findSolution();
	}
	
	
	public static void main(String[] args){
		//we will try to solve the problem in two ways. one is
		//straightforward (from the start to goal)  and one is 
		//backwards (goal to start), one of the solution (if
		//such solution will be found) we will return the
		//best solution of those two solutions (if a solution
		//will be found)

		//set the start and goal states

		//for(int itr=0;itr<=0;itr++){
			SlidingPuzzleState startState1 = new SlidingPuzzleState(args[0]);
			SlidingPuzzleState finalState1 = new SlidingPuzzleState(args[1]);

			SlidingPuzzleState startState2 = new SlidingPuzzleState(args[1]);
			SlidingPuzzleState finalState2 = new SlidingPuzzleState(args[0]);

			String output = args[2];
			int mode = Integer.valueOf(args[3]);

			PrimitiveCollection<SlidingPuzzleState> bank1 = null;
			PrimitiveCollection<SlidingPuzzleState> bank2 = null;

			Heuristic h1 = null;
			Heuristic h2 = null;

			//set the heuristics and the DataStructure who will
			//contain the states
			switch (mode){
			case 0: 
				h1 = new ImprovedMDHuristic(finalState1,20);
				bank1 = new BinaryHeap<SlidingPuzzleState>();
				h2 = new ImprovedMDHuristic(finalState2,20);
				bank2 = new BinaryHeap<SlidingPuzzleState>();
				break;
			case 1: 
				//we use Queue for the BFS
				h1 = new DummyHeuristic();
				h2 = new DummyHeuristic();
				bank1 = new PrimitiveQueue<SlidingPuzzleState>();
				break;
			}

			//set the totalFunction who will rank the whole state
			Heuristic totalFunction = new AStarMD();
			startState1.setHeuristics(h1,totalFunction);
			finalState1.setHeuristics(h1,totalFunction);

			startState1.rank();
			finalState1.rank();

			startState2.setHeuristics(h2,totalFunction);
			finalState2.setHeuristics(h2,totalFunction);

			//after setting the heuristics, rank the states
			startState2.rank();
			finalState2.rank();

			SolutionBank.setOutputPath(output);
			//create the instances of the Solvers
			SlidingPuzzle sp1 = new SlidingPuzzle(bank1,startState1,finalState1);
			SlidingPuzzle sp2 = new SlidingPuzzle(bank2,startState2,finalState2);
			sp2.setReversed(true);

			//if there are more than one processor, run multy threading
			//ssolution, if not run the methods one after another
			if (Runtime.getRuntime().availableProcessors()>1){
				new Thread(sp1).start();
				//iff we are running the A* algorithem, try to solve
				//the problem backwards
				if (mode==0){
					new Thread(sp2).start();
				}
			}else{
				SolutionInfo sol = sp1.findSolution();
				SolutionBank.init();
				SolutionBank.addSolution(sol);
				//iff we are running the A* algorithem try to solve
				//the problem backwards
				if(mode==0){
					if (sol==null || !sol.hasSolution()){
						SolutionBank.addSolution(sp2.findSolution());
					}else{
						SolutionBank.addSolution(sp2.findSolution(sol.getNodesExpantionNumber()*2));
					}
				}
				SolutionBank.loadFinalSolution();
				SolutionBank.printSolution();
			}
		//}
		for(SolutionInfo s:SolutionBank.getSolutionsList()){
			System.out.println("Sol length: "+s.getSolutionLength());
			System.out.println("##################");
		}



	}





}
